#ifndef PRETREE_H_
#define PRETREE_H_
#include <algorithm>
#include <cstddef>
#include <string>
#include <vector>

// 常见类实现
namespace trie1
{
constexpr const char alphabet[] = "abcdefghijklmnopqrstuvwsyz";

struct TrieNode {
    size_t                 pass;
    size_t                 end;
    std::vector<TrieNode*> nexts;
    TrieNode(size_t p = 0, size_t e = 0, const std::vector<TrieNode*>& n = std::vector<TrieNode*>{})
        : pass(p), end(e), nexts(n)
    {
    }
    ~TrieNode()
    {
        for (auto& i : nexts) {
            i = nullptr;
        }
    }
};

// 只接受小写字母
class Trie {
    TrieNode* root;

private:
    inline void create(const std::string& word)
    {
        if (word.empty()) return;
        TrieNode* cur = root;
        for (auto c : word) {
            int n = c - 'a';
            if (cur->nexts.empty() || cur->nexts[n] == nullptr) {
                if (cur->nexts.empty()) cur->nexts.resize(26);
                cur->nexts[n] = new TrieNode();
            }
            cur->pass++;
            cur = cur->nexts[n];
        }
        cur->pass++;
        cur->end++;
    }

    inline void destory(TrieNode*& node)
    {
        if (node->nexts.empty()) {
            delete node;
            node = nullptr;
            return;
        }
        for (auto& n : node->nexts) {
            n == nullptr ? (void)0 : destory(n);
            delete n;
            n = nullptr;
        }
        node->pass = 0;
        node->end  = 0;
        node->nexts.clear();
    }

public:
    Trie(const std::string& text)
    {
        root = new TrieNode(0, 0);
        std::string cur;
        for (int i = 0; i < text.size(); i++) {
            if (text[i] >= 'a' && text[i] <= 'z') {
                cur += text[i];
            }
            else {
                create(cur);
                cur = "";
            }
        }
        if (!cur.empty()) create(cur);
    }

    ~Trie()
    {
        destory(root);
        root = nullptr;
    }

    // 插入单词
    inline void insert(const std::string& word) { create(word); }

    // 从树中移除单词word
    inline void del(const std::string& word)
    {
        if (word.empty()) return;
        if (search(word) == 0) return;
        int       n   = word[0] - 'a';
        TrieNode* cur = root->nexts[n];
        TrieNode* pre = root;
        for (int i = 1; i < word.size(); i++) {
            n = word[i] - 'a';
            cur->pass--;
            if (cur->pass == 0) {
                n = word[i - 1] - 'a';
                break;
            }
            pre = cur;
            cur = cur->nexts[n];
        }
        destory(cur);
        TrieNode*& node = pre->nexts[n];
        node            = nullptr;
    }

    // 返回树中word的实例个数
    inline size_t search(const std::string& word) const
    {
        if (word.empty()) return 0;
        TrieNode* cur = root;
        for (int i = 0; i < word.size(); i++) {
            int n = word[i] - 'a';
            if (cur->nexts[n] == nullptr) return 0;
            cur = cur->nexts[n];
        }
        return cur->end;
    }

    // 树中有几个单词
    inline size_t all_words() const { return root->pass; }

    // 返回以prefix为前缀的单词有几个
    inline size_t prefix(const std::string& prefix) const
    {
        if (prefix.empty()) return 0;
        TrieNode* cur = root;
        for (int i = 0; i < prefix.size(); i++) {
            int n = prefix[i] - 'a';
            if (cur->nexts[n] != nullptr) {
                cur = cur->nexts[n];
            }
            else {
                return 0;
            }
        }
        return cur->pass;
    }
};
}   // namespace trie1

// 固定数组方式实现
namespace trie2
{
constexpr int MAXN = 150001;
class Trie {
    inline static int (*tree)[26] = new int[MAXN][26]{0};
    inline static int* pass       = new int[MAXN]{0};
    inline static int* end        = new int[MAXN]{0};
    inline static int  cnt        = 1;

public:
    Trie(const std::string& text)
    {
        if (text.empty()) return;
        std::string cur;
        for (size_t i = 0; i < text.size(); i++) {
            if (text[i] >= 'a' && text[i] <= 'z') {
                cur += text[i];
            }
            else {
                insert(cur);
                cur = "";
            }
        }

        if (!cur.empty()) insert(cur);
    }

    ~Trie()
    {
        for (int i = 1; i <= cnt; i++) {
            std::fill(&tree[i][0], &tree[i][25], 0);
            pass[i] = 0;
            end[i]  = 0;
        }
    }

    inline void insert(const std::string& word)
    {
        int cur = 1;
        pass[cur]++;
        for (int i = 0, path; i < word.size(); i++) {
            path = word[i] - 'a';
            if (tree[cur][path] == 0) tree[cur][path] = ++cnt;
            cur = tree[cur][path];
            pass[cur]++;
        }
        end[cur]++;
    }

    inline int search(const std::string& word) const
    {
        int cur = 1;
        for (int i = 0, path; i < word.size(); i++) {
            path = word[i] - 'a';
            if (tree[cur][path] == 0) return 0;
            cur = tree[cur][path];
        }
        return end[cur];
    }

    inline int prefix(const std::string& word) const
    {
        int cur = 1;
        for (int i = 0, path; i < word.size(); i++) {
            path = word[i] - 'a';
            if (tree[cur][path] == 0) return 0;
            cur = tree[cur][path];
        }
        return pass[cur];
    }

    inline void del(const std::string& word)
    {
        if (search(word) == 0) return;

        int cur = 1;
        pass[cur]--;
        for (int i = 0, path; i < word.size(); i++) {
            path = word[i] - 'a';
            if (--pass[tree[cur][path]] == 0) {
                tree[cur][path] = 0;
                return;
            }
            cur = tree[cur][path];
        }
        end[cur]--;
    }
};

}   // namespace trie2

#endif